package leetcode_81_100;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class inorderTraversal_94 {
    /**
     * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历
     * 按照访问左子树——根节点——右子树的方式
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        /**
         * 递归写法，通俗易懂
         */
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) { //若该节点是空，直接返回
            return;
        }
        inorder(root.left, res); //进入左节点
        res.add(root.val);//添加当前节点的值
        inorder(root.right, res); //进入右节点
    }





    /**
     * 颜色标记法。TreeNode类型表示第一次出入栈，int类型表示第二次出入栈
     * 有点像递归
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<Object> stack=new Stack<>();//注意，stack是可以弹入null值的，n个null值占n个位置
        stack.push(root);//根节点入栈

        while(!stack.isEmpty()){
            Object obj = stack.pop();
            if(obj instanceof TreeNode){  //当obj是TreeNode 类型是，说明第一次
                TreeNode node=(TreeNode) obj;
                if(node.right!=null){    //先进右节点，再进左节点，这样出栈时，该左节点先出栈
                    stack.push(node.right);
                }
                stack.push(node.val);//添加此时节点的值
                if(node.left!=null){
                    stack.push(node.left);
                }
            }
            //第二次出栈
            else{
                list.add((Integer) obj);
            }
        }

        return list;
    }
}
